/**************************************************************************
* File:            graphgen.h	                                          *
* Description:     Generators of diffent kinds of graphs                  *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/

#pragma once

#include "graph.h"
#include <vector>

std::vector<Edge> getRandomEdges(int n, double density, bool acyclic = false){
	int number_of_edges = density*n*n;
	std::vector<Edge> edges;

	for (int i = 0; i < number_of_edges; ++i){
		int x = rand() % n, y = rand() % n;
		if (acyclic && x > y)
			std::swap(x, y);

		edges.push_back(Edge(x, y));
	}


	std::sort(edges.begin(), edges.end());
	edges.resize(std::unique(edges.begin(), edges.end()) - edges.begin());

	return edges;
}

std::unique_ptr<Graph> getRandomGraph(int n, double density, bool acyclic = 0){
	return makeCompactGraph(getRandomEdges(n, density, acyclic), n);
}

std::unique_ptr<Graph> readGraph(){
	int n, m;
	std::vector<Edge> edges;
	std::cin >> n >> m;
	for (int i = 0, from, to; i < m; ++i){
		std::cin >> from >> to;
		edges.emplace_back(from, to);
	}

	return makeCompactGraph(edges, n);
}

std::unique_ptr<Graph> getFullGraph(int n){
	std::vector<Edge> edges;
	for (int i = 0; i < n; ++i)
	for (int j = i; j < n; ++j)
		edges.emplace_back(j, i);

	return makeCompactGraph(edges, n);
}

std::unique_ptr<Graph> getFunctionalGraph(int n, std::function<int(int)> f){
	std::vector<Edge> edges;
	for (int i = 0; i < n; ++i)
		edges.emplace_back(i, f(i) % n);
	return makeCompactGraph(edges, n);
}

std::vector<std::unique_ptr<Graph>> getAllGraphs(int size){
	int count = size*(size-1);
	int max_mask = (1 << count);
	std::vector<Edge> edges;
	std::vector<std::unique_ptr<Graph>> ans;

	for (int mask = 0; mask < max_mask; ++mask){
		int bit = 1;
		for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
		if (i != j){
			if (mask&bit)
				edges.emplace_back(i, j);
			bit <<= 1;
		}

		ans.push_back(makeCompactGraph(edges, size));
		edges.clear();
	}

	return ans;
}